1. Field
The present application relates generally to the operation of overlay networks, and more particularly, to methods and apparatus for enhanced overlay state maintenance in a peer-to-peer overlay network.
2. Background
A network in which member nodes obtain services in the absence of server-based infrastructure is referred to as a “peer-to-peer” overlay network. In a peer-to-peer overlay, peer nodes co-operate with each other to provide services and to maintain the network. Peer-to-peer overlay networks can be built on top of an underlying network, such as a network utilizing the Internet Protocol (IP).
In a peer-to-peer overlay network, each node has knowledge of one or more peers participating in the overlay. A simple but inefficient approach to routing data on the overlay network from a source node to a destination node is to continually pass the data to the next hop or successor node (i.e., node logically next to the source node in the identity space) until the destination node is reached. However this approach incurs excessive latency as the size of the overlay network and number of hops increases. Therefore, for routing optimization, each node maintains a list of fingers that are one node, two nodes, four nodes, or up to 2(m-1) nodes away from itself; where m is the number of bits assigned to each node identifier. This helps in minimizing the number of hops needed to route data from node O(n) to node O(log(n)) where n is the number of nodes for the average case.
However, nodes may come and go at any time and result in changes in the overlay network configuration that affects the fingers known to a particular node. To compensate for this variability, each node re-runs a finger stabilization algorithm that re-computes the fingers known to that node. The results of the finger stabilization algorithm are stored in a finger table. Unfortunately, since each node maintains it own finger table, determining the frequency at which each node needs to run its finger stabilization algorithm may be problematic. For example, if a node does not run its finger stabilization algorithm often enough, its finger table may become stale resulting in inefficient and delayed packet routing. If a node runs its finger stabilization algorithm too often, this may result in wasting overlay bandwidth and/or placing a burden on other nodes on the overlay network. For example, running the stabilization algorithm requires power, and excessive execution of the stabilization algorithm may waste power at battery operated nodes.
Furthermore, since structured peer-to-peer overlay networks are highly distributed in nature, participating nodes do not have complete routing tables and hence do not know the size of the overlay network they are operating in. However, knowledge of the size of the overlay network can be useful for several purposes, such as when merging overlays, performing load balancing or caching strategies, as well as routing protocol specialization.
Unfortunately, conventional systems may fail to provide an accurate overlay network size. For example, nodes may leave the overlay without gracefully notifying their neighbors, and as a result, the size of the overlay network may not be accurately maintained.
Therefore, it would be desirable to have a simple cost effective mechanism that operates to allow a node to adaptively schedule a finger stabilization algorithm and to determine the size of an overlay network to overcome the problems described above.